package collection

import "iter"

// LinkedList 泛型化双链表（无锁, 不适用于并发场景）
//   - 双链表由一个个数据节点组成的，要么它是空的，要么它存在两个指针，分别指向直接后继和直接前驱
//   - 双链表中有两个节点比较特殊，分别是头节点和尾节点
//   - 正常的双链表，不存在递归结构
//   - 操作性能略低于ContainerList, 泛型化便于使用，提供更多的便捷操作方法
type LinkedList[T any] struct {
	head *LinkedNode[T] // 头节点指向
	end  *LinkedNode[T] // 尾节点指向
	size int            // 链表长度
}

// LinkedNode 双链表节点
type LinkedNode[T any] struct {
	list  *LinkedList[T] // 所属的链表
	prev  *LinkedNode[T] // 上一个节点
	next  *LinkedNode[T] // 下一个节点
	value T
}

// NewLinkedList 创建一个空的双链表
func NewLinkedList[T any]() *LinkedList[T] {
	l := new(LinkedList[T])
	return l
}

// Head 取得头节点, 返回nil表示空的单链表
func (l *LinkedList[T]) Head() *LinkedNode[T] {
	return l.head
}

// Head 取得尾节点, 返回nil表示空的单链表
func (l *LinkedList[T]) End() *LinkedNode[T] {
	return l.end
}

// PushHead 添加节点到头部
//   - 返回插入的最后一个节点(头部节点)
func (l *LinkedList[T]) PushHead(values ...T) (newNode *LinkedNode[T]) {
	// 如果 values 为空，直接返回当前链表的头节点
	if len(values) == 0 {
		return l.head
	}
	for _, val := range values {
		newNode = &LinkedNode[T]{list: l, prev: nil, next: nil, value: val}
		if l.size == 0 {
			// 当前链表是空链表, Push为第一个节点
			l.head = newNode
			l.end = l.head
			l.size = 1
		} else {
			// 将新节点Push到头部
			l.head.prev = newNode
			newNode.next = l.head
			l.head = newNode // 更新头节点
			l.size++
		}
	}
	return
}

// PushEnd 添加节点到尾部
//   - 返回插入的最后一个节点(尾部节点)
func (l *LinkedList[T]) PushEnd(values ...T) (newNode *LinkedNode[T]) {
	// 如果 values 为空，直接返回当前链表的尾节点
	if len(values) == 0 {
		return l.end
	}
	for _, val := range values {
		newNode = &LinkedNode[T]{list: l, prev: nil, next: nil, value: val}
		if l.size == 0 || l.end == nil {
			// 当前链表是空链表, Push为第一个节点
			l.head = newNode
			l.end = l.head
			l.size = 1
		} else {
			// 将新节点Push到尾部
			l.end.next = newNode
			newNode.prev = l.end
			l.end = newNode // 更新尾节点
			l.size++
		}
	}
	return
}

// LinkedEnd 链表尾部连接上另一个链表
func (l *LinkedList[T]) LinkedEnd(other *LinkedList[T]) *LinkedList[T] {
	if other == nil || other.Size() == 0 {
		return l
	}
	// 遍历other链表, 插入到当且链表的头部
	for v := range other.IterHead() {
		l.PushEnd(v)
	}
	return l
}

// LinkedHead 链表头部连接上另一个链表
func (l *LinkedList[T]) LinkedHead(other *LinkedList[T]) *LinkedList[T] {
	if other == nil || other.Size() == 0 {
		return l
	}
	// 遍历other链表, 插入到当且链表的头部
	for v := range other.IterEnd() {
		l.PushHead(v)
	}
	return l
}

// 找到指定索引的节点和前一个节点
//   - 注意: 此方法为无锁操作，加锁操作由入口方法执行
//   - index索引从0开始, l.size-1 截止
//   - 当 index 为 0 时，获取头部节点
//   - 当 index 为 l.size-1 时，获取尾部节点
//   - 当链表为空或index索引越界时返回nil
func (l *LinkedList[T]) findWith(index int) (node *LinkedNode[T]) {
	// 检查链表是否为空
	if l.size == 0 {
		return nil
	}
	// 检查索引是否越界
	if index < 0 || index > l.size-1 {
		return nil
	}
	// 特殊情况：头节点或尾节点
	if index == 0 {
		return l.head
	}
	if index == l.size-1 {
		return l.end
	}
	// 从头或尾开始遍历，选择较短路径
	if index <= l.size/2 {
		for i, node := 0, l.head; node != nil; i++ {
			if i == index {
				return node
			}
			node = node.next
		}
	} else {
		for i, node := l.size-1, l.end; node != nil; i-- {
			if i == index {
				return node
			}
			node = node.prev
		}
	}
	// 没有找到
	return nil
}

// InsertAt 在指定索引位置插入新节点
//   - 注意: - index索引从0开始
//   - 当 index 为 0 时, 表示从头部位置开始插入
//   - 当 index 为 n 时, 表示从索引位置开始插入，索引位置节点及后续节点全部后移
//   - 当 index 为 l.size-1 时, 表示从尾部-1位置插入
//   - 当 index 为 l.size 时，表示从尾部插入
//   - 返回新插入的最后一个节点, 索引越界或插入失败返回nil
func (l *LinkedList[T]) InsertAt(index int, values ...T) (newNode *LinkedNode[T]) {
	// 无数据，返回 nil
	if len(values) == 0 {
		return nil
	}
	// 检查索引是否越界
	if index < 0 || index > l.size {
		return nil
	}
	// 特殊情况: 当链表是空链表, 直接插入到尾部
	// 特殊情况: 当index为 l.size 时，插入操作认为是合法的尾部插入
	if l.size == 0 || index == l.size {
		for _, val := range values {
			newNode = l.doInsertAtEnd(val)
			if newNode == nil {
				return nil
			}
		}
		return
	}
	// 特殊情况: 当索引为0时，直接插入到头部
	if index == 0 {
		for _, val := range values {
			newNode = l.doInsertAtHead(val)
			if newNode == nil {
				return nil
			}
		}
		return
	}
	// 特殊情况，当索引index==l.size-1且链表中只有1个节点元素，则直接插入到头部
	if l.size == 1 && index == l.size-1 {
		for _, val := range values {
			newNode = l.doInsertAtHead(val)
			if newNode == nil {
				return nil
			}
		}
		return
	}
	// 依据索引找到对应的节点
	var prevNode *LinkedNode[T]
	if index <= l.size/2 {
		prevNode = l.head
		for i := 0; i < index; i++ {
			prevNode = prevNode.next
		}
	} else {
		prevNode = l.end
		for i := l.size - 1; i > index; i-- {
			prevNode = prevNode.prev
		}
	}
	if prevNode == nil || prevNode.prev == nil {
		return nil
	}
	prevNode = prevNode.prev
	for _, val := range values {
		newNode = l.doInsertAtAfter(prevNode, val)
		if newNode == nil {
			return nil
		}
		prevNode = newNode
	}
	return
}

// InsertAtHead 在头部插入新节点
//   - 返回新插入的最后一个节点, 无数据或插入失败返回nil
func (l *LinkedList[T]) InsertAtHead(values ...T) (newNode *LinkedNode[T]) {
	// 如果 values 为空，直接返回nil
	if len(values) == 0 {
		return nil
	}
	for _, val := range values {
		newNode = l.doInsertAtHead(val)
		if newNode == nil {
			return nil
		}
	}
	return
}

// InsertAtEnd 在尾部插入新节点
//   - 返回新插入的最后一个节点（新的尾部节点）, 无数据或插入失败返回nil
func (l *LinkedList[T]) InsertAtEnd(values ...T) (newNode *LinkedNode[T]) {
	// 如果 values 为空，直接返回nil
	if len(values) == 0 {
		return nil
	}
	for _, val := range values {
		newNode = l.doInsertAtEnd(val)
		if newNode == nil {
			return nil
		}
	}
	return
}

// doInsertAtHead 在头部插入新节点
//   - 注意: 此方法为无锁操作，加锁操作由入口方法执行
func (l *LinkedList[T]) doInsertAtHead(val T) *LinkedNode[T] {
	newNode := &LinkedNode[T]{list: l, value: val}
	if l.size == 0 {
		l.head = newNode
		l.end = newNode
		l.size++
		return newNode
	}
	if l.size == 1 {
		l.head.prev = newNode
		l.end.prev = newNode
		newNode.next = l.end
		l.head = newNode
		l.size++
		return newNode
	}

	if l.head != nil {
		if l.head.next != nil {
			l.head.next.prev = newNode
		}
		newNode.next = l.head
		l.head.prev = newNode
	}
	l.head = newNode
	l.size++
	return newNode
}

// doInsertAtEnd 在尾部插入新节点
//   - 注意: 此方法为无锁操作，加锁操作由入口方法执行
func (l *LinkedList[T]) doInsertAtEnd(val T) *LinkedNode[T] {
	newNode := &LinkedNode[T]{list: l, value: val}
	if l.size == 0 {
		l.head = newNode
		l.end = newNode
		l.size++
		return newNode
	}
	if l.size == 1 {
		l.head.next = newNode
		l.end.prev = l.head
		l.end = newNode
		l.size++
		return newNode
	}
	l.end.next = newNode
	newNode.prev = l.end
	l.end = newNode
	l.size++
	return newNode
}

// doInsertAtAfter 在指定节点之后插入新节点
//   - 注意: 此方法为无锁操作，加锁操作由入口方法执行
func (l *LinkedList[T]) doInsertAtAfter(node *LinkedNode[T], val T) (newNode *LinkedNode[T]) {
	newNode = &LinkedNode[T]{value: val, prev: node, next: node.next}
	if node.next != nil {
		node.next.prev = newNode
	}
	node.next = newNode
	l.size++
	return newNode
}

// Get 取得指定链表索引的节点
//   - 注意index索引从0开始, l.size-1 截止
//   - 当 index 为 0 时，获取头部节点
//   - 当 index 为 l.size-1 时，获取尾部节点
func (l *LinkedList[T]) Get(index int) (node *LinkedNode[T]) {
	node = l.findWith(index)
	return
}

// Has 是否存在指定链表索引的节点
//   - 注意index索引从0开始, l.size-1 截止
func (l *LinkedList[T]) Has(index int) bool {
	// 检查链表是否为空
	if l.size == 0 {
		return false
	}
	// 检查索引是否越界
	if index < 0 || index > l.size-1 {
		return false
	}
	return true
}

// Delete 删除指定索引位置的节点
//   - 注意index索引从0开始, l.size-1 截止
func (l *LinkedList[T]) Delete(index int) bool {
	// 检查链表是否为空
	if l.size == 0 {
		return false
	}
	// 检查索引是否越界
	if index < 0 || index > l.size-1 {
		return false
	}
	// 特殊情况：删除头节点
	if index == 0 {
		l.head.prev = nil // avoid memory leaks
		l.head.list = nil
		l.head = l.head.next
		if l.head != nil {
			l.head.prev = nil
		} else {
			l.end.prev = nil // avoid memory leaks
			l.end.next = nil
			l.end.list = nil
			l.end = nil
		}
		l.size--
		return true
	}
	// 特殊情况：删除尾节点
	if index == l.size-1 {
		l.end.next = nil // avoid memory leaks
		l.end.list = nil
		l.end = l.end.prev
		if l.end != nil {
			l.end.next = nil
		} else {
			l.head.prev = nil // avoid memory leaks
			l.head.next = nil
			l.head.list = nil
			l.head = nil
		}
		l.size--
		return true
	}
	// 从头或尾节点开始遍历找到指定索引的节点
	var node *LinkedNode[T]
	if index < l.size/2 {
		// 从头节点开始遍历
		for i, n := 0, l.head; n != nil; n = n.next {
			if i == index {
				node = n
				break
			}
			i++
		}
	} else {
		// 从尾节点开始遍历
		for i, n := l.size-1, l.end; n != nil; n = n.prev {
			if i == index {
				node = n
				break
			}
			i--
		}
	}
	// 未找到节点，返回 false
	if node == nil {
		return false
	}
	// 删除节点(断开前后节点的链接)
	node.prev.next = node.next
	node.next.prev = node.prev
	node.next = nil // avoid memory leaks
	node.prev = nil // avoid memory leaks
	node.list = nil
	l.size--
	return true
}

// Reverse 反转双向链表节点
func (l *LinkedList[T]) Reverse() {
	// 如果链表为空，无需反转
	if l.size < 1 {
		l.size = 0
		l.head, l.end = nil, nil
		return
	}
	// 如果链表只有一个节点，直接更新头尾指针
	if l.size == 1 {
		l.head, l.end = l.end, l.head
		return
	}
	// 使用两个指针，分别指向当前节点和前一个节点
	var prev, curr *LinkedNode[T]
	curr = l.head
	for curr != nil {
		next := curr.next
		curr.next, curr.prev = prev, next
		prev, curr = curr, next
	}
	// 更新头尾指针
	l.head, l.end = l.end, l.head
}

// Clear 清空链表
func (l *LinkedList[T]) Clear() {
	if l.size == 0 {
		return
	}
	// 遍历链表，释放每个节点的内存，直到链表为空
	for current := l.head; current != nil; {
		next := current.next
		current.next = nil // 将节点设为 nil，快速完成垃圾回收
		current = next
	}
	// 重置链表的头、尾指针和大小
	l.head = nil
	l.end = nil
	l.size = 0
}

// Clone 复制链表 (节点Value浅拷贝)
func (l *LinkedList[T]) Clone() *LinkedList[T] {
	if l.size == 0 {
		return NewLinkedList[T]()
	}
	// 创建新的链表
	newList := NewLinkedList[T]()
	newList.head = &LinkedNode[T]{list: newList, value: l.head.value, next: nil, prev: nil}
	newList.end = newList.head
	newList.size = 1
	// 遍历剩余节点，复制到新链表
	for node := l.head.next; node != nil; node = node.next {
		newNode := &LinkedNode[T]{list: newList, value: node.value, next: nil, prev: newList.end}
		newList.end.next = newNode
		newList.end = newNode
		newList.size++
	}
	return newList
}

// Values 取得链表所有节点的切片值
func (l *LinkedList[T]) Values() (values []T) {
	// 使用 append 方法动态扩展切片，避免预先分配过大的内存，提高性能。
	values = make([]T, 0, l.size)
	for node := l.head; node != nil; node = node.next {
		values = append(values, node.value)
	}
	return
}

// Size 链表长度
func (l *LinkedList[T]) Size() int {
	return l.size
}

// IsEmpty 链表是否为空
func (l *LinkedList[T]) IsEmpty() bool {
	return l.size == 0
}

// PopHead 出列消费数据，返回列表头部节点的数据, 同时移除已消费的头部节点
func (l *LinkedList[T]) PopHead() (val T, ok bool) {
	if l.head != nil {
		val = l.head.value
		ok = true
		l.head.doRemove() // 移除当前节点
	}
	return
}

// PopEnd 出列消费数据，返回列表尾部节点的数据, 同时移除已消费的尾部节点
func (l *LinkedList[T]) PopEnd() (val T, ok bool) {
	if l.end != nil {
		val = l.end.value
		ok = true
		l.end.doRemove() // 移除当前节点
	}
	return
}

// IterHead 链表节点数据迭代器(从头部开始)
//   - 使用 for v:=range LinkedList.IterHead(){}
func (l *LinkedList[T]) IterHead() iter.Seq[T] {
	return func(yield func(val T) bool) {
		for node := l.head; node != nil; node = node.next {
			if !yield(node.value) {
				return
			}
		}
	}
}

// IterEnd 链表节点数据迭代器(从尾部开始)
//   - 使用 for v:=range LinkedList.IterEnd(){}
func (l *LinkedList[T]) IterEnd() iter.Seq[T] {
	return func(yield func(val T) bool) {
		for node := l.end; node != nil; node = node.prev {
			if !yield(node.value) {
				return
			}
		}
	}
}

// IterHeadAndPop 链表节点数据迭代并消费数据(从头部开始)
//   - 迭代同时移除已消费的节点
//   - 使用 for v:=range LinkedList.IterHeadAndPop(){}
func (l *LinkedList[T]) IterHeadAndPop() iter.Seq[T] {
	return func(yield func(val T) bool) {
		for node := l.head; node != nil; node = l.head {
			val := node.value
			node.doRemove()
			if !yield(val) {
				return
			}
		}
	}
}

// IterEndAndPop 链表节点数据迭代并消费数据(从尾部开始)
//   - 迭代同时移除已消费的节点
//   - 使用 for v:=range LinkedList.IterEndAndPop(){}
func (l *LinkedList[T]) IterEndAndPop() iter.Seq[T] {
	return func(yield func(val T) bool) {
		for node := l.end; node != nil; node = l.end {
			val := node.value
			node.doRemove()
			if !yield(val) {
				return
			}
		}
	}
}

// Remove 删除当前节点(删除自己)
func (n *LinkedNode[T]) Remove() bool {
	return n.doRemove()
}

// doRemove 删除当前节点(无锁操作)
func (n *LinkedNode[T]) doRemove() bool {
	if n == nil || n.list == nil {
		return false
	}
	// 链表长度减一
	n.list.size--
	// 检查当前链表长度
	if n.list.size == 0 {
		// 当前节点为是链表唯一的1个节点
		n.list.head = nil
		n.list.end = nil
		//n = nil
		return true
	}

	// 处理头节点
	if n == n.list.head {
		n.list.head = n.next
		if n.list.head != nil {
			n.list.head.prev = nil
		}
		//n = nil
		return true
	}

	// 处理尾节点
	if n == n.list.end {
		n.list.end = n.prev
		if n.list.end != nil {
			n.list.end.next = nil
		}
		//n = nil
		return true
	}
	// 处理中间节点
	n.prev.next = n.next
	n.next.prev = n.prev
	n.next = nil // avoid memory leaks
	n.prev = nil // avoid memory leaks
	n.list = nil
	return true
}

// InsertAfter 基于当前节点之后添加节点
//   - 返回插入是新节点
func (n *LinkedNode[T]) InsertAfter(value T) *LinkedNode[T] {
	return n.doInsertAfter(value)
}

// doInsertAfter 基于当前节点之后添加节点(无锁操作)
//   - 返回插入是新节点
func (n *LinkedNode[T]) doInsertAfter(value T) (newNode *LinkedNode[T]) {
	if n == nil || n.list == nil {
		// 处理 n 或 n.list 为 nil 的情况
		return nil
	}
	newNode = &LinkedNode[T]{list: n.list, value: value}
	newNode.prev = n
	newNode.next = n.next
	if n.next != nil {
		n.next.prev = newNode
	} else {
		// n 是尾节点
		n.list.end = newNode // 更新尾节点
	}
	n.next = newNode
	n.list.size++
	return
}

// InsertBefore 基于当前节点之前添加节点
//   - 返回插入是新节点
func (n *LinkedNode[T]) InsertBefore(value T) *LinkedNode[T] {
	return n.doInsertBefore(value)
}

// doInsertBefore 基于当前节点之前添加节点(无锁操作)
//   - 返回插入是新节点
func (n *LinkedNode[T]) doInsertBefore(value T) (newNode *LinkedNode[T]) {
	newNode = &LinkedNode[T]{list: n.list, value: value}
	// 更新新节点的 next 指针
	newNode.next = n

	// 更新新节点的 prev 指针
	if n.prev != nil {
		n.prev.next = newNode
		newNode.prev = n.prev
	} else {
		// n 是头节点，更新链表的头指针
		n.list.head = newNode
		newNode.prev = nil
	}

	// 更新当前节点的 prev 指针
	n.prev = newNode
	n.list.size++
	return
}

// List 取得节点所属链表对象
func (n *LinkedNode[T]) List() (list *LinkedList[T]) {
	if n == nil || n.list == nil {
		// 处理 n 或 n.list 为 nil 的情况
		return
	}
	return n.list
}

// Next 获取Next节点
//   - 返回nil表示到达链表的末尾
func (n *LinkedNode[T]) Next() (node *LinkedNode[T]) {
	if n == nil || n.list == nil {
		// 处理 n 或 n.list 为 nil 的情况
		return
	}
	return n.next
}

// Prev 获取Prev节点
//   - 返回nil表示到达链表的头部
func (n *LinkedNode[T]) Prev() (node *LinkedNode[T]) {
	if n == nil || n.list == nil {
		// 处理 n 或 n.list 为 nil 的情况
		return
	}
	return n.prev
}

// Head 取得尾节点, 返回nil表示空的单链表
func (n *LinkedNode[T]) Head() (node *LinkedNode[T]) {
	if n == nil || n.list == nil {
		// 处理 n 或 n.list 为 nil 的情况
		return
	}
	return n.list.head
}

// End 取得尾节点, 返回nil表示空的单链表
func (n *LinkedNode[T]) End() (node *LinkedNode[T]) {
	if n == nil || n.list == nil {
		// 处理 n 或 n.list 为 nil 的情况
		return
	}
	return n.list.end
}

// Value 取得节点值
func (n *LinkedNode[T]) Value() (val T) {
	if n == nil || n.list == nil {
		// 处理 n 或 n.list 为 nil 的情况
		return
	}
	return n.value
}
